1. Field of the Invention
The invention relates to a calculation unit for executing at least one part of a cryptographic protocol including determining the inverse of an integer modulo a large number.
The invention relates more particularly to means for determining this kind of inverse quickly.
2. Description of the Prior Art
Some cryptographic protocols, for example those known as the Digital Signature Algorithm (DSA) and the Elliptic Curve DSA (ECDSA), have to calculate the inverse of a random integer modulo a large number repetitively. For more details on such protocols see IEEE publication P1363/D13 and especially sections 6.2.7 and 7.2.7 thereof. The aforementioned large number is denoted N in the remainder of this description.
Two numbers are the inverse of each other if their product is identically equal to 1 modulo said large number. For example, the numbers 3 and 5 are the inverse of each other modulo 14. This is because 3×5=15≡1 modulo 14.
One prior art method of performing this calculation is based on the following equation:y=x−1=xφ(N)−1  modulo Nin which φ(N) is the number of integers prime with N and less than N. This is Euler's “totient” function.
If N is prime, the following simplification is valid:φ(N)=N−1and consequently:y=x−1=xN−2 
In binary, this calculation requires 3n/2 multiplications of n×n bits where n=log2 N, in other words of the order of 160 multiplications in practice.
The invention proposes a faster calculation method in which two numbers that are the inverse of each other modulo N are generated at the same time, by a specific calculation, for example based on a random number.